// https://leetcode.cn/problems/longest-univalue-path/
// Created by ade on 2022/9/2.
//
#include <iostream>
#include <vector>
#include <unordered_map>


using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode() : val(0), left(nullptr), right(nullptr) {}

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    unordered_map<TreeNode *, int> m = {};// 贡献点
    int maxN = 0;

    int longestUnivaluePath1(TreeNode *root) {
        dfs(root);
        for (auto i : m) {
            cout << "node:" << i.first->val << ",val:" << i.second << endl;
        }
        return maxN;
    }

    /*
     *  if (root == nullptr) {
            return 0;
        }
        int left = dfs(root->left), right = dfs(root->right);
        int left1 = 0, right1 = 0;
        if (root->left && root->left->val == root->val) {
            left1 = left + 1;
        }
        if (root->right && root->right->val == root->val) {
            right1 = right + 1;
        }
        res = max(res, left1 + right1);
        return max(left1, right1)
     * */
    // 自己的做法，空间复杂度O(N)
    void dfs(TreeNode *node) {
        if (!node) return;
        dfs(node->left);
        dfs(node->right);
        if (m.find(node) == m.end()) m[node] = 0;
        int left = 0;
        if (node->left && node->val == node->left->val) {
            left = m[node->left] + 1;
        }
        int right = 0;
        if (node->right && node->val == node->right->val) {
            right = m[node->right] + 1;
        }
        m[node] = max(left, right);
        maxN = max(maxN, left + right);
    }


    int longestUnivaluePath(TreeNode *root) {
        dfs1(root);
        return maxN;
    }

    int dfs1(TreeNode *node) {
        if (!node) return 0;
        int left = dfs1(node->left);
        int right = dfs1(node->right);
        // 因为本身节点和左节点或者右节点不一致，所以需要新建一个变量单独记录
        int l = 0, r = 0;
        if (node->left && node->left->val == node->val) {
            l = left + 1;
        }
        if (node->right && node->right->val == node->val) {
            r = right + 1;
        }
        maxN = max(maxN, l + r);
        return max(l, r);
    }

    TreeNode *init() {
        TreeNode *h1 = new TreeNode(5);
        TreeNode *h2 = new TreeNode(5);
        TreeNode *h3 = new TreeNode(5);
        TreeNode *h4 = new TreeNode(1);
        TreeNode *h5 = new TreeNode(4);
        TreeNode *h6 = new TreeNode(1);
        h1->left = h5;
        h1->right = h2;
        h5->left = h4;
        h5->right = h6;
        h2->right = h3;

        return h1;
    }
};

int main() {
    Solution so;
    TreeNode *h = so.init();
    cout << so.longestUnivaluePath(h) << endl;
    return 0;
}